The testing of a complex software system typically requires a large number of test cases, generally based on a user-defined test specification. For the purpose of automated test generation, one approach is to express the test specification ina a special language or notation that embodies a representation of the structure and the format of test cases. Examples of known test generators developed primarily for the purpose of compiler testing can be found, for example, in the following: F. Bazzichi and I. Spadafora, "An Automatic Generator for Compiler Testing," IEEE Transactions on Software Engineering, Vol. SE-8, pp. 343-353, 1982; Ronald F. Guilmette, "TGGS: A Flexible System for Generating Efficient Test Case Generators", March 1995, world-wide-web document available at an ftp site (ftp://ftp.ccnet.com/users/rfg/products/tggs/tggs-paper.ps); and P. M. Maurer, "Generating Test Data with Enhanced Context-Free Grammars", IEEE Software, pp. 50-55, 1990.
One way of encoding a test specification is as a context-free grammar. Introductory and descriptive material on context-free grammar may be found, for example, in "Pushdown Automata Theory", particularly Chapter 13 thereof. Additional background material is found in William Homer et al., "Independent Testing of Compiler Phases Using a Test Case Generator", Software--Practice and Experience, Vol. 19(1), pp. 53-62, January, 1989; Peter M. Maurer, "The Design and Implementation of a Grammar-based Data Generator", Software--Practice and Experience, Vol. 23(3), pp. 223-244, March, 1992; A. G. Duncan et al., "Using Attributed Grammars to Test Designs and Implementations", CH1627-9/81/0000/0170500.75, 1981 IEEE; U.S. Pat. No. 4,729,096, entitled METHOD AND APPARATUS FOR GENERATING A TRANSLATOR PROGRAM FOR A COMPILER/INTERPRETER AND FOR TESTING THE RESULTING TRANSLATOR PROGRAM, issued Mar. 1, 1988 in the name of Larson; U.S. Pat. No. 5,067,129, entitled SERVICE PROCESSOR TESTER, issued Nov. 19, 1991 in the name of Evans et al.; U.S. Pat. No. 5,414,836, entitled SOFTWARE TESTING SYSTEM THAT EMPLOYS A GRAPHICAL INTERFACE TO GENERATE TEST CASES CONFIGURED AS HYBRID TREE STRUCTURES, issued May 9, 1995 in the name of Baer et al.